What you have, not who you know: food-enhanced social capital and changes in social behavioural relationships in a non-human primate.

Social network position in non-human primates has far-reaching fitness consequences. Critically, social networks are both heterogeneous and dynamic, meaning an individual's current network position is likely to change due to both intrinsic and extrinsic factors. However, our understanding of the drivers of changes in social network position is largely confined to opportunistic studies. Experimental research on the consequences of in situ, controlled network perturbations is limited. Here we conducted a food-based experiment in rhesus macaques to assess whether allowing an individual the ability to provide high-quality food to her group changed her social behavioural relationships. We considered both her social network position across five behavioural networks, as well as her dominance and kin interactions. We found that gaining control over a preferential food resource had far-reaching social consequences. There was an increase in both submission and aggression centrality and changes in the socio-demographic characteristics of her agonistic interaction partners. Further, we found that her grooming balance shifted in her favour as she received more grooming than she gave. Together, these results provide a novel, preliminary insight into how in situ, experimental manipulations can modify social network position and point to broader network-level shifts in both social capital and social power.

Input node placement restricting the longest control chain in controllability of complex networks.

The minimum number of inputs needed to control a network is frequently used to quantify its controllability. Control of linear dynamics through a minimum set of inputs, however, often has prohibitively large energy requirements and there is an inherent trade-off between minimizing the number of inputs and control energy. To better understand this trade-off, we study the problem of identifying a minimum set of input nodes such that controllabililty is ensured while restricting the length of the longest control chain. The longest control chain is the maximum distance from input nodes to any network node, and recent work found that reducing its length significantly reduces control energy. We map the longest control chain-constraint minimum input problem to finding a joint maximum matching and minimum dominating set. We show that this graph combinatorial problem is NP-complete, and we introduce and validate a heuristic approximation. Applying this algorithm to a collection of real and model networks, we investigate how network structure affects the minimum number of inputs, revealing, for example, that for many real networks reducing the longest control chain requires only few or no additional inputs, only the rearrangement of the input nodes.

A multiplex centrality metric for complex social networks: sex, social status, and family structure predict multiplex centrality in rhesus macaques.

Members of a society interact using a variety of social behaviors, giving rise to a multi-faceted and complex social life. For the study of animal behavior, quantifying this complexity is critical for understanding the impact of social life on animals' health and fitness. Multilayer network approaches, where each interaction type represents a different layer of the social network, have the potential to better capture this complexity than single layer approaches. Calculating individuals' centrality within a multilayer social network can reveal keystone individuals and more fully characterize social roles. However, existing measures of multilayer centrality do not account for differences in the dynamics and functionality across interaction layers. Here we validate a new method for quantifying multiplex centrality called consensus ranking by applying this method to multiple social groups of a well-studied nonhuman primate, the rhesus macaque. Consensus ranking can suitably handle the complexities of animal social life, such as networks with different properties (sparse vs. dense) and biological meanings (competitive vs. affiliative interactions). We examined whether individuals' attributes or socio-demographic factors (sex, age, dominance rank and certainty, matriline size, rearing history) were associated with multiplex centrality. Social networks were constructed for five interaction layers (i.e., aggression, status signaling, conflict policing, grooming and huddling) for seven social groups. Consensus ranks were calculated across these five layers and analyzed with respect to individual attributes and socio-demographic factors. Generalized linear mixed models showed that consensus ranking detected known social patterns in rhesus macaques, showing that multiplex centrality was greater in high-ranking males with high certainty of rank and females from the largest families. In addition, consensus ranks also showed that females from very small families and mother-reared (compared to nursery-reared) individuals were more central, showing that consideration of multiple social domains revealed individuals whose social centrality and importance might otherwise have been missed.

Competitive percolation strategies for network recovery.

Restoring operation of critical infrastructure systems after catastrophic events is an important issue, inspiring work in multiple fields, including network science, civil engineering, and operations research. We consider the problem of finding the optimal order of repairing elements in power grids and similar infrastructure. Most existing methods either only consider system network structure, potentially ignoring important features, or incorporate component level details leading to complex optimization problems with limited scalability. We aim to narrow the gap between the two approaches. Analyzing realistic recovery strategies, we identify over- and undersupply penalties of commodities as primary contributions to reconstruction cost, and we demonstrate traditional network science methods, which maximize the largest connected component, are cost inefficient. We propose a novel competitive percolation recovery model accounting for node demand and supply, and network structure. Our model well approximates realistic recovery strategies, suppressing growth of the largest connected component through a process analogous to explosive percolation. Using synthetic power grids, we investigate the effect of network characteristics on recovery process efficiency. We learn that high structural redundancy enables reduced total cost and faster recovery, however, requires more information at each recovery step. We also confirm that decentralized supply in networks generally benefits recovery efforts.

Exotic states in a simple network of nanoelectromechanical oscillators.

Synchronization of oscillators, a phenomenon found in a wide variety of natural and engineered systems, is typically understood through a reduction to a first-order phase model with simplified dynamics. Here, by exploiting the precision and flexibility of nanoelectromechanical systems, we examined the dynamics of a ring of quasi-sinusoidal oscillators at and beyond first order. Beyond first order, we found exotic states of synchronization with highly complex dynamics, including weak chimeras, decoupled states, traveling waves, and inhomogeneous synchronized states. Through theory and experiment, we show that these exotic states rely on complex interactions emerging out of networks with simple linear nearest-neighbor coupling. This work provides insight into the dynamical richness of complex systems with weak nonlinearities and local interactions.

Talent and experience shape competitive social hierarchies.

The hierarchy of social organization is a ubiquitous property of animal and human groups, linked to resource allocation, collective decisions, individual health, and even to social instability. Experimental evidence shows that both the intrinsic abilities of individuals and social reinforcement processes impact hierarchies; existing mathematical models, however, focus on the latter. Here, we develop a rigorous model that incorporates both features and explore their synergistic effect on stability and the structure of hierarchy. For pairwise interactions, we show that there is a trade-off between relationship stability and having the most talented individuals in the highest ranks. Extending this to open societies, where individuals enter and leave the population, we show that important societal effects arise from the interaction between talent and social processes: (i) Despite a positive global correlation between talent and rank, paradoxically, local correlation is negative, and (ii) the removal of an individual can induce a series of rank reversals. We show that the mechanism underlying the latter is the removal of an older individual of limited talent, who nonetheless was able to suppress the rise of younger, more talented individuals.

Controllability of multiplex, multi-time-scale networks.

The paradigm of layered networks is used to describe many real-world systems, from biological networks to social organizations and transportation systems. While recently there has been much progress in understanding the general properties of multilayer networks, our understanding of how to control such systems remains limited. One fundamental aspect that makes this endeavor challenging is that each layer can operate at a different time scale; thus, we cannot directly apply standard ideas from structural control theory of individual networks. Here we address the problem of controlling multilayer and multi-time-scale networks focusing on two-layer multiplex networks with one-to-one interlayer coupling. We investigate the practically relevant case when the control signal is applied to the nodes of one layer. We develop a theory based on disjoint path covers to determine the minimum number of inputs (N_{i}) necessary for full control. We show that if both layers operate on the same time scale, then the network structure of both layers equally affect controllability. In the presence of time-scale separation, controllability is enhanced if the controller interacts with the faster layer: N_{i} decreases as the time-scale difference increases up to a critical time-scale difference, above which N_{i} remains constant and is completely determined by the faster layer. We show that the critical time-scale difference is large if layer I is easy and layer II is hard to control in isolation. In contrast, control becomes increasingly difficult if the controller interacts with the layer operating on the slower time scale and increasing time-scale separation leads to increased N_{i}, again up to a critical value, above which N_{i} still depends on the structure of both layers. This critical value is largely determined by the longest path in the faster layer that does not involve cycles. By identifying the underlying mechanisms that connect time-scale difference and controllability for a simplified model, we provide crucial insight into disentangling how our ability to control real interacting complex systems is affected by a variety of sources of complexity.

Patterns of patterns of synchronization: Noise induced attractor switching in rings of coupled nonlinear oscillators.

Following the long-lived qualitative-dynamics tradition of explaining behavior in complex systems via the architecture of their attractors and basins, we investigate the patterns of switching between distinct trajectories in a network of synchronized oscillators. Our system, consisting of nonlinear amplitude-phase oscillators arranged in a ring topology with reactive nearest-neighbor coupling, is simple and connects directly to experimental realizations. We seek to understand how the multiple stable synchronized states connect to each other in state space by applying Gaussian white noise to each of the oscillators' phases. To do this, we first analytically identify a set of locally stable limit cycles at any given coupling strength. For each of these attracting states, we analyze the effect of weak noise via the covariance matrix of deviations around those attractors. We then explore the noise-induced attractor switching behavior via numerical investigations. For a ring of three oscillators, we find that an attractor-switching event is always accompanied by the crossing of two adjacent oscillators' phases. For larger numbers of oscillators, we find that the distribution of times required to stochastically leave a given state falls off exponentially, and we build an attractor switching network out of the destination states as a coarse-grained description of the high-dimensional attractor-basin architecture.

Connecting core percolation and controllability of complex networks.

Core percolation is a fundamental structural transition in complex networks related to a wide range of important problems. Recent advances have provided us an analytical framework of core percolation in uncorrelated random networks with arbitrary degree distributions. Here we apply the tools in analysis of network controllability. We confirm analytically that the emergence of the bifurcation in control coincides with the formation of the core and the structure of the core determines the control mode of the network. We also derive the analytical expression related to the controllability robustness by extending the deduction in core percolation. These findings help us better understand the interesting interplay between the structural and dynamical properties of complex networks.

Do the rich get richer? An empirical analysis of the Bitcoin transaction network.

The possibility to analyze everyday monetary transactions is limited by the scarcity of available data, as this kind of information is usually considered highly sensitive. Present econophysics models are usually employed on presumed random networks of interacting agents, and only some macroscopic properties (e.g. the resulting wealth distribution) are compared to real-world data. In this paper, we analyze Bitcoin, which is a novel digital currency system, where the complete list of transactions is publicly available. Using this dataset, we reconstruct the network of transactions and extract the time and amount of each payment. We analyze the structure of the transaction network by measuring network characteristics over time, such as the degree distribution, degree correlations and clustering. We find that linear preferential attachment drives the growth of the network. We also study the dynamics taking place on the transaction network, i.e. the flow of money. We measure temporal patterns and the wealth accumulation. Investigating the microscopic statistics of money movement, we find that sublinear preferential attachment governs the evolution of the wealth distribution. We report a scaling law between the degree and wealth associated to individual nodes.

Emergence of bimodality in controlling complex networks.

Our ability to control complex systems is a fundamental challenge of contemporary science. Recently introduced tools to identify the driver nodes, nodes through which we can achieve full control, predict the existence of multiple control configurations, prompting us to classify each node in a network based on their role in control. Accordingly a node is critical, intermittent or redundant if it acts as a driver node in all, some or none of the control configurations. Here we develop an analytical framework to identify the category of each node, leading to the discovery of two distinct control modes in complex systems: centralized versus distributed control. We predict the control mode for an arbitrary network and show that one can alter it through small structural perturbations. The uncovered bimodality has implications from network security to organizational research and offers new insights into the dynamics and control of complex systems.

Effect of correlations on network controllability.

A dynamical system is controllable if by imposing appropriate external signals on a subset of its nodes, it can be driven from any initial state to any desired state in finite time. Here we study the impact of various network characteristics on the minimal number of driver nodes required to control a network. We find that clustering and modularity have no discernible impact, but the symmetries of the underlying matching problem can produce linear, quadratic or no dependence on degree correlation coefficients, depending on the nature of the underlying correlations. The results are supported by numerical simulations and help narrow the observed gap between the predicted and the observed number of driver nodes in real networks.

Core percolation on complex networks.

We analytically solve the core percolation problem for complex networks with arbitrary degree distributions. We find that purely scale-free networks have no core for any degree exponents. We show that for undirected networks if core percolation occurs then it is continuous while for directed networks it is discontinuous (and hybrid) if the in- and out-degree distributions differ. We also find that core percolations on undirected and directed networks have completely different critical exponents associated with their critical singularities.

EEG synchronization characteristics of functional connectivity and complex network properties of memory maintenance in the delta and theta frequency bands.

Task-dependent changes of nonlinear-linear synchronization features and graph theoretical properties of the delta and theta frequencies were analyzed in the present EEG study that were related to episodic memory maintenance processes. Synchronization was found to increase with respect to both the delta and theta bands within the frontal and parietal areas and also between these regions. Results of graph theoretical analysis indicated a task-related shift towards small-world network topology in the theta band.

Shortest path discovery of complex networks.

In this Rapid Communication we present an analytic study of sampled networks in the case of some important shortest-path sampling models. We present analytic formulas for the probability of edge discovery in the case of an evolving and a static network model. We also show that the number of discovered edges in a finite network scales much more slowly than predicted by earlier mean-field models. Finally, we calculate the degree distribution of sampled networks and we demonstrate that they are analogous to a destroyed network obtained by randomly removing edges from the original network.